package sort;

import utils.FileUtils;
import utils.SortUtils;

//希尔排序
public class ShellSort {
    public static void main(String[] args) {
        // 需要加载的排序的文件，n-普通版本，数据范围在int范围内，1k - 1000个数据的文件
//        String fileName = "n_1k";
//		String fileName = "n_1w";
//        String fileName = "n_10w";
        String fileName = "n_100w";
//		String fileName = "n_500w";

        // 数据文件加载
        long startTime = System.currentTimeMillis();
        String readText = FileUtils.readText(SortUtils.FILE_PREFIX + fileName);
        String[] numString = readText.split(" ");
        long endTime = System.currentTimeMillis();
        System.out.println(fileName + "数据文件加载共耗时：" + (endTime - startTime) + "ms");

        // 基数排序
        startTime = System.currentTimeMillis();
        int[] num = shellSort(numString);
        endTime = System.currentTimeMillis();
        System.out.println(fileName + "数据进行希尔排序共耗时：" + (endTime - startTime) + "ms");

        // 正确性验证
        startTime = System.currentTimeMillis();
        SortUtils.validate(num);
        endTime = System.currentTimeMillis();
        System.out.println(fileName + "希尔排序正确性验证共耗时：" + (endTime - startTime) + "ms");
    }

    // 希尔排序
    public static int[] shellSort(String[] numString) {
        int[] arr = new int[numString.length];
        for (int i = 0; i < numString.length; i++) {
            arr[i] = Integer.valueOf(numString[i]);
        }
        sort(arr);
        return arr;
    }

    private static void sort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = 0; i < gap; i++) {
                int flag = 0;
                do {
                    flag = 0;
                    for (int k = i + gap; k < arr.length; k += gap) {
                        if (arr[k] < arr[k - gap]) {
                            int temp = arr[k];
                            arr[k] = arr[k - gap];
                            arr[k - gap] = temp;
                            flag = 1;
                        }
                    }
                } while (flag == 1);
            }
        }
    }
}
